package oct2013;

import java.util.HashMap;

public class LongestConsecutiveSequence {
	public int longestConsecutive(int[] num) {
		int n = num.length;
		boolean[] used = new boolean[n];
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
		for (int i = 0; i < n; ++i) {
			map.put(num[i], i);
		}
		int max = 0;
		for (int i = 0; i < n; ++i) {
			if (map.get(num[i]) != i || used[i])
				continue;
			int v = num[i];
			used[i] = true;
			while (map.containsKey(v - 1)) {
				v--;
				used[map.get(v)] = true;
			}
			int u = num[i];
			while (map.containsKey(u + 1)) {
				u++;
				used[map.get(u)] = true;
			}
			max = Math.max(max, u - v + 1);
		}
		return max;
	}
}
